{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Set Intersection Size At Least Two"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intersectionSizeTwo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #设置交集大小至少为2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>intervals</code> ，其中 <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 表示从 <code>start<sub>i</sub></code> 到 <code>end<sub>i</sub></code> 的所有整数，包括 <code>start<sub>i</sub></code> 和 <code>end<sub>i</sub></code> 。</p>\n",
    "\n",
    "<p><strong>包含集合</strong> 是一个名为 <code>nums</code> 的数组，并满足 <code>intervals</code> 中的每个区间都 <strong>至少</strong> 有 <strong>两个</strong> 整数在 <code>nums</code> 中。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>intervals = [[1,3], [3,7], [8,9]]</code> ，那么 <code>[1,2,4,7,8,9]</code> 和 <code>[2,3,4,8,9]</code> 都符合 <strong>包含集合</strong> 的定义。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回包含集合可能的最小大小。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,3],[3,7],[8,9]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>nums = [2, 3, 4, 8, 9].\n",
    "可以证明不存在元素数量为 4 的包含集合。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,3],[1,4],[2,5],[3,5]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>nums = [2, 3, 4].\n",
    "可以证明不存在元素数量为 2 的包含集合。 \n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,2],[2,3],[2,4],[4,5]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>nums = [1, 2, 3, 4, 5].\n",
    "可以证明不存在元素数量为 4 的包含集合。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= intervals.length &lt;= 3000</code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [set-intersection-size-at-least-two](https://leetcode.cn/problems/set-intersection-size-at-least-two/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [set-intersection-size-at-least-two](https://leetcode.cn/problems/set-intersection-size-at-least-two/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[3,7],[8,9]]', '[[1,3],[1,4],[2,5],[3,5]]', '[[1,2],[2,3],[2,4],[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        res=[]\n",
    "        for s,t in intervals:\n",
    "            if len(res)>=2 and res[-2]>=s:\n",
    "                continue\n",
    "            if len(res)>=1 and res[-1]>=s:\n",
    "                if t==res[-1]:\n",
    "                    res.pop()\n",
    "                    res.append(t-1)\n",
    "                res.append(t)\n",
    "            else:\n",
    "                res.append(t-1)\n",
    "                res.append(t)\n",
    "            # print(res)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        intervals.reverse()\n",
    "        s=set()\n",
    "        ans=0\n",
    "        #last=float(\"inf\")\n",
    "        last1=float(\"inf\")\n",
    "        last2=float(\"inf\")\n",
    "        for a,b in intervals:\n",
    "            #print(a,b,last1,last2)\n",
    "            if last2<=b:\n",
    "                continue\n",
    "            elif last1<=b:\n",
    "                if a!=last1:\n",
    "                    last1,last2=a,last1\n",
    "                else:\n",
    "                    last1,last2=a,a+1\n",
    "                ans+=1\n",
    "            else:\n",
    "                last1,last2=a,a+1\n",
    "                ans+=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[1], -x[0]))\n",
    "        res = 0\n",
    "        p1, p2 = float('-inf'), float('-inf')\n",
    "        for first, last in intervals:\n",
    "            if p2 < first:\n",
    "                res += 2\n",
    "                p1 = last-1\n",
    "                p2 = last\n",
    "            elif p2 == first:\n",
    "                res += 1\n",
    "                p1 = first\n",
    "                p2 = last\n",
    "            elif p1 < first:\n",
    "                res += 1\n",
    "                p1 = p2\n",
    "                p2 = last\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        cur, next = intervals[-1][0], intervals[-1][0] + 1\n",
    "        res = 2\n",
    "        for x, y in reversed(intervals[:-1]):\n",
    "            if y >= next:\n",
    "                continue\n",
    "            elif y < cur:\n",
    "                cur = x\n",
    "                next = x + 1\n",
    "                res += 2\n",
    "            elif cur <= y < next:\n",
    "                next = cur\n",
    "                cur = x\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        # 右端点从小到大，保证贪心处理边缘点的正确性，同时右端点一样的时候优先处理长度最短的区间，因为该区间可选点最少\n",
    "        intervals.sort(key=lambda x:(x[1], -x[0]))\n",
    "        a, b, ans = -1, -1, 0\n",
    "        for start, end in intervals:\n",
    "            if start > b: # 不重合\n",
    "                a, b, ans = end-1, end, ans + 2\n",
    "            elif start > a: # start肯定在[a,b]之间\n",
    "                a = b # 至少保证前一个区间有两个点被覆盖\n",
    "                b = end # 贪心\n",
    "                ans += 1\n",
    "            # 剩下情况为 start <= a, 由于end >= b(intervals右侧从小到大排序)，所以a,b肯定在当前区间中\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals = sorted(intervals, key=lambda x:[x[1], -x[0]])\n",
    "        end = intervals[0][1]\n",
    "        pre_end = end-1\n",
    "        out = 2\n",
    "        for x, y in intervals[1:]:\n",
    "            if x <= pre_end:\n",
    "                continue\n",
    "            if x <= end:\n",
    "                out += 1\n",
    "                pre_end = end\n",
    "                end = y\n",
    "            else:\n",
    "                out += 2\n",
    "                pre_end = y-1\n",
    "                end = y\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key = lambda x: (x[0], - x[1]))\n",
    "        needs = [2] * n \n",
    "        res = 0\n",
    "        while intervals:\n",
    "            s, e = intervals.pop() \n",
    "            need = needs.pop()\n",
    "            for p in range(s, s + need):\n",
    "                for i in range(len(needs) - 1, - 1, - 1):\n",
    "                    if intervals[i][1] < p:\n",
    "                        break\n",
    "                    if needs[i] > 0:\n",
    "                        needs[i] -= 1 \n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        m = sorted(intervals,key= lambda x:x[0])\n",
    "        ans = [m[-1][0],m[-1][0]+1]\n",
    "        l = len(m)\n",
    "        if l == 1:\n",
    "            return 2\n",
    "        def inn(x,y):\n",
    "            if x>=y[0] and x <= y[1]:\n",
    "                return True\n",
    "            return False\n",
    "        for i in range(l-2,-1,-1):\n",
    "            if inn(ans[0],m[i]) and not inn(ans[1],m[i]):\n",
    "                for j in range(m[i][0],m[i][1]+1):\n",
    "                    if j not in set(ans):\n",
    "                        ans = [j] + ans\n",
    "                        if ans[1]<ans[0]:\n",
    "                            t = ans[1]\n",
    "                            ans[1]=ans[0]\n",
    "                            ans[0]=t\n",
    "                        break\n",
    "            elif not inn(ans[0],m[i]) and not inn(ans[1],m[i]):\n",
    "                ans = [m[i][0],m[i][0]+1] + ans\n",
    "            #print(ans)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        if not intervals:\n",
    "            return 0\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        ans = 2\n",
    "        cur, next = intervals[-1][0], intervals[-1][0] + 1\n",
    "        for x, y in reversed(intervals[:-1]):\n",
    "            if y >= next:\n",
    "                continue\n",
    "            elif y < cur:\n",
    "                cur = x\n",
    "                next = x + 1\n",
    "                ans += 2\n",
    "            elif cur <= y < next:\n",
    "                next = cur\n",
    "                cur = x\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x : (x[0], -x[1]))\n",
    "        n = len(intervals)\n",
    "        val = [list() for _ in range(n)] \n",
    "        ans = 0 \n",
    "        for i in range(n-1, -1, -1):\n",
    "            j = intervals[i][0]\n",
    "            tmp = []\n",
    "            for k in range(len(val[i]), 2):\n",
    "                ans += 1 \n",
    "                for p in range(i-1, -1, -1):\n",
    "                    if intervals[p][1] < j:\n",
    "                        break \n",
    "                    val[p].append(j+k)\n",
    "                j+=1\n",
    "            #val[i] += tmp \n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        dp=sorted(intervals,key=lambda x:(x[0],-x[1]))\n",
    "        ans=2\n",
    "        cur=dp[-1][0]\n",
    "        cur2=dp[-1][0]+1\n",
    "        def ju(a,b,c):\n",
    "            if a>=b and a<=c:\n",
    "                return True\n",
    "            return False\n",
    "        for i in range(len(dp)-2,-1,-1):\n",
    "            if ju(cur2,dp[i][0],dp[i][1]):\n",
    "                continue\n",
    "            elif ju(cur,dp[i][0],dp[i][1]):\n",
    "                ans+=1\n",
    "                cur2=cur\n",
    "                cur=dp[i][0]\n",
    "            else:\n",
    "                ans+=2\n",
    "                cur=dp[i][0]\n",
    "                cur2=cur+1            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: x[1])\n",
    "        # print(intervals)\n",
    "        pre = -1\n",
    "        prepre = -2\n",
    "        ans = 0\n",
    "        for l, r in intervals:\n",
    "            if l >= pre:\n",
    "                if l > pre:\n",
    "                    pre = r\n",
    "                    prepre = r - 1\n",
    "                    ans += 2\n",
    "                else:\n",
    "                    prepre = pre\n",
    "                    pre = r\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if l > prepre:\n",
    "                    prepre = pre\n",
    "                    pre = r\n",
    "                    ans += 1\n",
    "            # print(pre, prepre)\n",
    "        return ans                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key = lambda x: (x[0], - x[1]))\n",
    "        needs = [2] * n \n",
    "        res = 0\n",
    "        while intervals:\n",
    "            s, e = intervals.pop() \n",
    "            need = needs.pop()\n",
    "            for p in range(s, s + need):\n",
    "                for i in range(len(needs) - 1, - 1, - 1):\n",
    "                    if intervals[i][1] < p:\n",
    "                        break\n",
    "                    if needs[i] > 0:\n",
    "                        needs[i] -= 1 \n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda x: ( x[0], -x[1]))\n",
    "        #print(intervals) \n",
    "        a = b = float('inf')\n",
    "        ans = 0 \n",
    "        for i in range(n-1, -1, -1):\n",
    "            if b <= intervals[i][1]:\n",
    "                continue \n",
    "            elif a > intervals[i][1]:\n",
    "                ans += 2 \n",
    "                a = intervals[i][0]\n",
    "                b = a + 1 \n",
    "            elif a == intervals[i][1]:\n",
    "                ans += 1\n",
    "                b = a \n",
    "                a = intervals[i][0] \n",
    "            elif intervals[i][0] <= a < intervals[i][1]:\n",
    "                if b > intervals[i][1]:\n",
    "                    ans += 1\n",
    "                    b = a \n",
    "                    a = intervals[i][0]\n",
    "            \n",
    "\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023-09-23 21:53:18\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, a: List[List[int]]) -> int:\n",
    "        a.sort(key=lambda e: (e[0], -e[1]))\n",
    "        x = a[-1][0]\n",
    "        y = x + 1\n",
    "        res = 2\n",
    "        for i in range(len(a) - 2, -1, -1):\n",
    "            left, right = a[i]\n",
    "            if left == x or right >= y:\n",
    "                continue\n",
    "            if right < x:\n",
    "                res += 2\n",
    "                x, y = left, left + 1\n",
    "                continue\n",
    "            res += 1\n",
    "            x, y = left, x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:(x[1], -x[0]))\n",
    "        n = len(intervals)\n",
    "        res = 2\n",
    "        end = intervals[0][1]\n",
    "        pre_end = end - 1\n",
    "        for i in range(1,n):\n",
    "            x, y = intervals[i][0], intervals[i][1]\n",
    "            if x<=pre_end:\n",
    "                continue\n",
    "            elif pre_end < x <=end:\n",
    "                res += 1\n",
    "                pre_end, end = end, y\n",
    "            else:\n",
    "                res += 2\n",
    "                pre_end, end = y-1, y\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\r\n",
    "        intervals.sort(key=lambda x:(x[0],-x[1]))\r\n",
    "        ans=0\r\n",
    "        L=len(intervals)\r\n",
    "        vals=[0]*L\r\n",
    "        for i in range(L-1,-1,-1):\r\n",
    "            j=intervals[i][0]\r\n",
    "            for k in range(vals[i],2):\r\n",
    "                ans+=1\r\n",
    "                for p in range(i-1,-1,-1):\r\n",
    "                    if intervals[p][1]<j:\r\n",
    "                        break\r\n",
    "                    vals[p]+=1\r\n",
    "                j+=1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        # 右端点升序，左端点降序（若右端点相同，则前面的是小区间，后面是大区间）\n",
    "        # pre_end 和 end 是包含集合中的最后两个元素\n",
    "        intervals.sort(key=lambda x:(x[1], -x[0]))\n",
    "        n = len(intervals)\n",
    "        res = 2\n",
    "        end = intervals[0][1]\n",
    "        pre_end = end - 1\n",
    "        for i in range(1,n):\n",
    "            x, y = intervals[i][0], intervals[i][1]\n",
    "            if x<=pre_end:\n",
    "                continue\n",
    "            elif pre_end < x <=end:\n",
    "                res += 1\n",
    "                pre_end, end = end, y\n",
    "            else:\n",
    "                res += 2\n",
    "                pre_end, end = y-1, y\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort()\n",
    "        intervals.reverse()\n",
    "        s=set()\n",
    "        ans=0\n",
    "        #last=float(\"inf\")\n",
    "        last1=float(\"inf\")\n",
    "        last2=float(\"inf\")\n",
    "        for a,b in intervals:\n",
    "            print(a,b,last1,last2)\n",
    "            if last2<=b:\n",
    "                continue\n",
    "            elif last1<=b:\n",
    "                if a!=last1:\n",
    "                    last1,last2=a,last1\n",
    "                else:\n",
    "                    last1,last2=a,a+1\n",
    "                ans+=1\n",
    "            else:\n",
    "                last1,last2=a,a+1\n",
    "                ans+=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        #for interval, chose 2 p, \n",
    "        intervals.sort(key=(lambda x: x[1]))\n",
    "        ans = [intervals[0][1]-1, intervals[0][1]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            s, e = intervals[i]\n",
    "            if s > ans[-1]:\n",
    "                ans.append(e-1)\n",
    "                ans.append(e)\n",
    "            elif s == ans[-1]:\n",
    "                ans.append(e)\n",
    "            else: #s < lastnum, \n",
    "                if s > ans[-2]:\n",
    "                    if ans[-1] == e: \n",
    "                        ans.append(e-1)\n",
    "                        ans[-1], ans[-2] = ans[-2], ans[-1]\n",
    "                    else:\n",
    "                        ans.append(e)\n",
    "                continue\n",
    "        # print(ans)\n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self,intervals):\n",
    "        intervals.sort(key=lambda x: (x[1], -x[0]))\n",
    "        res = 0\n",
    "        cur = [-1, -1]\n",
    "        for start, end in intervals:\n",
    "            if start > cur[1]:\n",
    "                cur = [end - 1, end]\n",
    "                res += 2\n",
    "            elif start > cur[0]:\n",
    "                cur = [cur[1], end]\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        #for interval, chose 2 p, \n",
    "        intervals.sort(key=(lambda x: x[1]))\n",
    "        ans = [intervals[0][1]-1, intervals[0][1]]\n",
    "        for i in range(1, len(intervals)):\n",
    "            s, e = intervals[i]\n",
    "            if s > ans[-1]:\n",
    "                ans.append(e-1)\n",
    "                ans.append(e)\n",
    "            elif s == ans[-1]:\n",
    "                ans.append(e)\n",
    "            else: #s < lastnum, \n",
    "                if s > ans[-2]:\n",
    "                    if ans[-1] == e: \n",
    "                        ans.append(e-1)\n",
    "                        ans[-1], ans[-2] = ans[-2], ans[-1]\n",
    "                    else:\n",
    "                        ans.append(e)\n",
    "                continue\n",
    "        print(ans)\n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        for i in range(len(intervals)):\n",
    "            intervals[i][0],intervals[i][1]=intervals[i][1],intervals[i][0]\n",
    "        intervals.sort()\n",
    "        pick=[]\n",
    "        for interval in intervals:\n",
    "            if pick==[]:\n",
    "                pick=[interval[0]-1,interval[0]]\n",
    "                continue\n",
    "            if pick[-1]>=interval[1] and pick[-1]<=interval[0]:\n",
    "                if pick[-2]>=interval[1] and pick[-2]<=interval[0]: \n",
    "                    continue\n",
    "                pick.append(interval[0])\n",
    "                if pick[-1]==pick[-2]:\n",
    "                    pick[-2]-=1\n",
    "                continue\n",
    "            pick.append(interval[0]-1)\n",
    "            pick.append(interval[0])\n",
    "        #print(intervals)\n",
    "        #print(pick)\n",
    "        return len(pick)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        # Sort intervals by their ending points.\n",
    "        # If two intervals have the same ending points, sort by the starting point in descending order.\n",
    "        intervals.sort(key=lambda x: (x[1], -x[0]))\n",
    "\n",
    "        res = []\n",
    "        for start, end in intervals:\n",
    "            # Check how many numbers from the current interval are already in the result.\n",
    "            covered = sum(start <= num <= end for num in res[-2:])\n",
    "\n",
    "            # If less than 2 numbers are covered, add missing numbers to the result.\n",
    "            for _ in range(2 - covered):\n",
    "                res.append(end - (2 - covered) + 1)\n",
    "                covered += 1\n",
    "\n",
    "        return len(res)\n",
    "\n",
    "# Test cases\n",
    "s = Solution()\n",
    "print(s.intersectionSizeTwo([[6,21],[1,15],[15,20],[10,21],[0,7]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals)\n",
    "        intervals.sort(key=lambda x: ( x[0], -x[1]))\n",
    "        print(intervals) \n",
    "        a = b = float('inf')\n",
    "        ans = 0 \n",
    "        for i in range(n-1, -1, -1):\n",
    "            if b <= intervals[i][1]:\n",
    "                continue \n",
    "            elif a > intervals[i][1]:\n",
    "                ans += 2 \n",
    "                a = intervals[i][0]\n",
    "                b = a + 1 \n",
    "            elif a == intervals[i][1]:\n",
    "                ans += 1\n",
    "                b = a \n",
    "                a = intervals[i][0] \n",
    "            elif intervals[i][0] <= a < intervals[i][1]:\n",
    "                if b > intervals[i][1]:\n",
    "                    ans += 1\n",
    "                    b = a \n",
    "                    a = intervals[i][0]\n",
    "            \n",
    "\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: x[1])\n",
    "        print(intervals)\n",
    "        pre = -1\n",
    "        prepre = -2\n",
    "        ans = 0\n",
    "        for l, r in intervals:\n",
    "            if l >= pre:\n",
    "                if l > pre:\n",
    "                    pre = r\n",
    "                    prepre = r - 1\n",
    "                    ans += 2\n",
    "                else:\n",
    "                    prepre = pre\n",
    "                    pre = r\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if l > prepre:\n",
    "                    prepre = pre\n",
    "                    pre = r\n",
    "                    ans += 1\n",
    "            # print(pre, prepre)\n",
    "        return ans                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x: (x[0], -x[1]))\n",
    "        #排序起始点越小, 结束点越大排序越前\n",
    "        ans, n, m = 0, len(intervals), 2\n",
    "        print(intervals)\n",
    "        vals = [[] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1): #从后往前遍历\n",
    "            j = intervals[i][0] #获取当前区间的起始点\n",
    "            for k in range(len(vals[i]), m): #vals[当前区间]里面元素数量未到达2, 进循环\n",
    "                ans += 1 #答案+1\n",
    "                for p in range(i - 1, -1, -1): #从当前区间向前找\n",
    "                    if intervals[p][1] < j: #如果遍历区间的最大值小于当前区间的最小值(不相交)\n",
    "                        break\n",
    "                    vals[p].append(j) #将目前的起始点加到vals[遍历区间]\n",
    "                j += 1\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
